#include <iostream>
#include <vector>

using namespace std;

// Definition for a QuadTree node.
class Node
{
public:
    bool val;
    bool isLeaf;
    Node *topLeft;
    Node *topRight;
    Node *bottomLeft;
    Node *bottomRight;

    Node()
    {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf)
    {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }

    Node(bool _val, bool _isLeaf, Node *_topLeft, Node *_topRight, Node *_bottomLeft, Node *_bottomRight)
    {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};

class Solution
{
public:
    Node *construct(vector<vector<int>> &grid)
    {
        return construct(grid, 0, 0, grid.size());
    }

    Node *construct(vector<vector<int>> &grid, int x, int y, int length)
    {
        if (length == 1)
        {
            return new Node(grid[x][y], true);
        }
        bool isSame = true;
        for (int i = x; i < x + length; i++)
        {
            for (int j = y; j < y + length; j++)
            {
                if (grid[i][j] != grid[x][y])
                {
                    isSame = false;
                    break;
                }
            }
        }
        if (isSame)
        {
            return new Node(grid[x][y], true);
        }
        Node *tl = construct(grid, x, y, length / 2);
        Node *tr = construct(grid, x, y + length / 2, length / 2);
        Node *bl = construct(grid, x + length / 2, y, length / 2);
        Node *br = construct(grid, x + length / 2, y + length / 2, length / 2);
        return new Node(true, false, tl, tr, bl, br);
    }
};
int main()
{
    cout << "Code427" << endl;
    Solution s;
    vector<vector<int>> grid = {{1, 1, 1, 1, 0, 0, 0, 0},
                                {1, 1, 1, 1, 0, 0, 0, 0},
                                {1, 1, 1, 1, 1, 1, 1, 1},
                                {1, 1, 1, 1, 1, 1, 1, 1},
                                {1, 1, 1, 1, 1, 1, 1, 1},
                                {1, 1, 1, 1, 1, 1, 1, 1},
                                {1, 1, 1, 1, 0, 0, 0, 0},
                                {1, 1, 1, 1, 0, 0, 0, 0}};
    Node *root = s.construct(grid);
    return 0;
}